package william.binarysearch;

/**
 * @author ZhangShenao
 * @date 2024/1/18
 * @description
 */
public class Leetcode162_寻找峰值 {
    /**
     * 借助二分查找的思想
     * Step1: 校验首、尾两个元素是否是峰值
     * Step2: 如果首、尾元素均不是峰值,说明nums[0] < nums[1],且nums[n-1] < nums[n-2],数组整体呈先上升、后下降的趋势,则中间部分一定存在峰值
     * Step3: 找到数组中间位置元素,判断其是否为峰值,如果是,则直接返回
     * Step4: 如果中间位置元素 < 前一个元素,则数组在左半部分呈先上升、后下降的趋势,则左半部分一定存在峰值,可以直接将右半部分丢弃
     * Step5: 同理.如果中间位置元素 < 后一个元素,则右半部分一定存在峰值,可以直接将左半部分丢弃
     * Step6: 持续上述过程,直到找到峰值
     */
    public int findPeakElement(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length == 0) {
            throw new RuntimeException("illegal input!");
        }

        if (nums.length == 1) {
            return 0;
        }

        int N = nums.length;

        //首先校验首、尾元素
        if (nums[0] > nums[1]) {
            return 0;
        }
        if (nums[N - 1] > nums[N - 2]) {
            return N - 1;
        }

        //如果首、尾元素均不是峰值,说明nums[0] < nums[1],且nums[n-1] < nums[n-2],数组整体呈先上升、后下降的趋势,则中间部分一定存在峰值
        //采用二分查找思想,
        int L = 0;
        int R = N - 1;
        while (L < R - 1) {  //确保区间内至少有3个元素 [L,R-1,R]
            int mid = L + ((R - L) >> 1);

            //校验中间位置元素
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            }

            //如果中间位置元素 < 前一个元素,则数组在中点的左半部分呈先上升、后下降的趋势,则左半部分一定存在峰值,可以直接将右半部分丢弃
            if (nums[mid] < nums[mid - 1]) {
                R = mid - 1;
            } else {    //反正同理,可将右半部分抛弃
                L = mid + 1;
            }
        }

        //最后返回区间内元素较大的索引
        return nums[L] > nums[R] ? L : R;
    }
}
